/*
** FileName:1673_找出最具竞争力的子序列.c
** Author:Creat
** Time:${Time}
**
**/
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
// 获得最小值的位置
int get_min_pos(int* nums, int start, int numsSize){
    int min = INT_MAX;
    int min_pos = -1;
    for(int i = start;i < numsSize;i++){
        if(nums[i] < min){
            min = nums[i];
            min_pos = i;
        }
    }
    return min_pos;
}
/*int* mostCompetitive(int* nums, int numsSize, int k, int* returnSize) {
    int* res = (int*)malloc(sizeof (int) * k);
    memset(res, 0, sizeof(int) * k);
    int start = 0;
    for(int i = 0;i < k;i++){
        start = get_min_pos(nums, start, numsSize - k + 1 + i);
        res[i] = nums[start];
        start++;
    }
    *returnSize = k;
    return res;
}*/
// 高效解法，贪心 + 单调栈 或者 单调队列
int* mostCompetitive(int* nums, int numsSize, int k, int* returnSize) {
    int* res = (int*)malloc(sizeof (int) * numsSize); // 这里扩大为 numsSize ，因为入栈的数量可能大于k
    memset(res, 0, sizeof(int) * numsSize);
    int pos = 0;
    for(int i = 0;i < numsSize;i++){
        while(pos > 0 && numsSize - i + pos > k && res[pos - 1] > nums[i])
            pos--;
        res[pos++] = nums[i];
    }
    *returnSize = k;
    return res;
}
//int main(void){
//    int nums[] = {3,5,2,6};
//    int res_size = 0;
//    int *res = NULL;
//    res = mostCompetitive(nums, 4,2,&res_size);
//    for(int i = 0;i < res_size;i++){
//        printf("%d\t", res[i]);
//    }
//    free(res);
//    return 0;
//}